package algorithm;

/**
 * @author MaGuangQi
 * @description: leetcode 236题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 * @date 2020-06-29 22:08
 **/
public class LowestCommonAncestor {
    /**
    *使用递归的三部曲
     * 1.找递归的终止条件
     * 2.找返回值,返回给上层的值
     * 3.单次的过程,(只考虑当前的过程)
     *
     *         3
     *        / \
     *       5   1
     *      / \  / \
     *     6  2  0  8
     *       / \
     *      7   4
     *
     * 注意看结果:
     *LCA(3,1)结果为3   情况一
     *LCA(1,3)结果为3  说明只要其中一个节点和根相等,那个根就是他们的公共祖先
     *LCA(5,1)结果为3 分部在3的左右子树中
     *LCA(6,8)结果为3 分部在3的左右子树中
     *LCA(8,7) = 3　　//分布在3的左右子树中　
     *LCA(6,4) = 5   　 //分布在5的左右子树中
     *LCA(5,2) = 5　    //其中一个节点与5相等
     *
     * 以某个节点为根节点,如果两个指定节点分别在根节点的两侧,那个次根节点就是他们的最近公共祖先
     * 如果两个指定节点在根节点的一端,说明当前根节点不是解,但是解肯定在它的某一端包含解,某一端不包含解
     *
     *如果root为空,或者root==p或者root==q,直接返回root,对应情况一
     *
     * 如果没有情况一返回,说明root不为空,并且root不等于p,也不等于q
     *   分以下情况
     *  一: 一个节点分布在root的左子树,一个分布在root的右子树
     *  二: 两个节点都位于root的左子树
     *  三: 两个节点都位于root的右子树
     *
     *  分别对左右子树进行递归.左右节点分别成为新root节点.(记为新root节点)
     *
     *  两个子树的返回值left和right有不同的情况
     *   一:left和right都不为空,对应情况一
     *   二:left为空,right不为空,对应情况三 两个节点都位于root的右子树
     *   三:left不为空,right为空,对应情况二 两个节点都位于root的左子树
     *
    */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            System.out.println("root是:null" + " p是:" + p.val + " q是:" + q.val);
        } else {
            System.out.println("root是:"+root.val+" p是:"+p.val+" q是:"+q.val);
        }

        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) { //情况一
            return root;
        }
        if (left != null) {   //情况二
            return left;
        }
        return right; //情况三
    }

    public static void main(String[] args) {
        LowestCommonAncestor l = new LowestCommonAncestor();
        TreeNode treeNode=new TreeNode(3);
        TreeNode treeNode1=new TreeNode(5);
        TreeNode treeNode2=new TreeNode(1);
        TreeNode treeNode3=new TreeNode(6);
        TreeNode treeNode4=new TreeNode(2);
        TreeNode treeNode5=new TreeNode(0);
        TreeNode treeNode6=new TreeNode(8);
        TreeNode treeNode7=new TreeNode(7);
        TreeNode treeNode8=new TreeNode(4);
        treeNode4.left=treeNode7;
        treeNode4.right=treeNode8;
        treeNode1.left=treeNode3;
        treeNode1.right=treeNode4;
        treeNode2.left=treeNode5;
        treeNode2.right=treeNode6;
        treeNode.left=treeNode1;
        treeNode.right=treeNode2;
        TreeNode treeNode9 = l.lowestCommonAncestor(treeNode, treeNode, treeNode2);
        System.out.println("最终结果"+treeNode9.val);
    }



    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
